Advances in Collaborative Filtering.
Abstract. Social networks are growing in number and size, with hundreds of millions of user accounts among them. One added benefit of these networks is that they allow users to encode more information about their relationships than just stating who they know. In this work, we are particularly interested in trust relationships, and how they can be used in designing interfaces. In this paper, we present FilmTrust, a website that uses trust in webbased social networks to create predictive movie recommendations. Using the FilmTrust system as a foundation, we show that these recommendations are more accurate than other techniques when the user&#039;s opinions about a film are divergent from the average. We discuss this technique both as an application of social network analysis, as well as how it suggests other analyses that can be performed to help improve collaborative filtering algorithms of all types. 1
On bootstrapping recommender systems.
For the past two years, we have been investigating the use of recommender systems as a technology in support of knowledge sharing in organizations. Recommender systems are a way of extending the natural process of recommendation by word-of-mouth to networked groups of people. They are able to provide personalized recommendations that take into account similarities between people based on their user profiles. The community around recommender systems that has emerged in the past five or so years has focused on methods for constructing and learning user profiles, the exploration and testing of various recommendation algorithms, and the design of user interfaces, with applications primarily in the domains of electronic commerce and leisure/entertainment. Thus far, we have...
Workshop on information heterogeneity and fusion in recommender systems %28HetRec 2010%29.

Performance of recommender algorithms on top%2Dn recommendation tasks.

Collaborative filtering with temporal dynamics.

Factor in the neighbors Scalable and accurate collaborative filtering.

Collaborative filtering with temporal dynamics.

Extending the spring%2Delectrical model to overcome warping effects.

Recommender systems for the conference paper assignment problem.
We present a recommender systems approach to conference paper assignment, i.e., the task of assigning paper submissions to reviewers. We address both the modeling of reviewerpaper preferences (which can be cast as a learning problem) and the optimization of reviewing assignments to satisfy global conference criteria (which can be viewed as constraint satisfaction). Due to the paucity of preference data per reviewer or per paper (relative to other recommender systems applications) we show how we can integrate multiple sources of information to learn reviewer-paper preference models. Our models are evaluated not just in terms of prediction accuracy but in terms of end-assignment quality. Using a linear programming-based assignment optimization, we show how our approach better explores the space of unsupplied assignments to maximize the overall affinities of papers assigned to reviewers. We demonstrate our results on real reviewer bidding data from the IEEE ICDM 2007 conference.
Recommender Systems for the Conference Paper Assignment Problem
We present a recommender systems approach to conference paper assignment, i.e., the task of assigning paper submissions to reviewers. We address both the modeling of reviewerpaper preferences (which can be cast as a learning problem) and the optimization of reviewing assignments to satisfy global conference criteria (which can be viewed as constraint satisfaction). Due to the paucity of preference data per reviewer or per paper (relative to other recommender systems applications) we show how we can integrate multiple sources of information to learn reviewer-paper preference models. Our models are evaluated not just in terms of prediction accuracy but in terms of end-assignment quality. Using a linear programming-based assignment optimization, we show how our approach better explores the space of unsupplied assignments to maximize the overall affinities of papers assigned to reviewers. We demonstrate our results on real reviewer bidding data from the IEEE ICDM 2007 conference.
Constrained graph layout by stress majorization and gradient projection.
 
The Binary Stress Model for Graph Drawing.

Collaborative Filtering for Implicit Feedback Datasets.
A common task of recommender systems is to improve customer experience through personalized recommendations based on prior implicit feedback. These systems passively track different sorts of user behavior, such as purchase history, watching habits and browsing activity, in order to model user preferences. Unlike the much more extensively researched explicit feedback, we do not have any direct input from the users regarding their preferences. In particular, we lack substantial evidence on which products consumer dislike. In this work we identify unique properties of implicit feedback datasets. We propose treating the data as indication of positive and negative preference associated with vastly varying confidence levels. This leads to a factor model which is especially tailored for implicit feedback recommenders. We also suggest a scalable optimization procedure, which scales linearly with the data size. The algorithm is used successfully within a recommender system for television shows. It compares favorably with well tuned implementations of other known methods. In addition, we offer a novel way to give explanations to recommendations given by this factor model. 1
Factorization meets the neighborhood a multifaceted collaborative filtering model.

Tutorial on recent progress in collaborative filtering.

Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights.

Fast direction%2Daware proximity for graph mining.
In this paper we study asymmetric proximity measures on directed graphs, which quantify the relationships between two nodes or two groups of nodes. The measures are useful in several graph mining tasks, including clustering, link prediction and connection subgraph discovery. Our proximity measure is based on the concept of escape probability. This way, we strive to summarize the multiple facets of nodes-proximity, while avoiding some of the pitfalls to which alternative proximity measures are susceptible. A unique feature of the measures is accounting for the underlying directional information. We put a special emphasis on computational efficiency, and develop fast solutions that are applicable in several settings. Our experimental study shows the usefulness of our proposed direction-aware proximity method for several applications, and that our algorithms achieve a significant speedup (up to 50,000x) over straightforward implementations.
Modeling relationships at multiple scales to improve accuracy of large recommender systems.

Lessons from the Netflix prize challenge.

Measuring and extracting proximity graphs in networks.
Measuring distance or some other form of proximity between objects is a standard data mining tool. Connection subgraphs were recently proposed as a way to demonstrate proximity between nodes in networks. We propose a new way of measuring and extracting proximity in networks called “cycle free effective conductance” (CFEC). Importantly, the measured proximity is accompanied with a proximity subgraph, which allows assessing and understanding measured values. Our proximity calculation can handle more than two endpoints, directed edges, is statistically well-behaved, and produces an effectiveness score for the computed subgraphs. We provide an efficient algorithm to measure and extract proximity. Also, we report experimental results and show examples for four large network data sets: a telecommunications calling graph, the IMDB actors graph, an academic co-authorship network, and a movie recommendation system.
Improved Circular Layouts.
Circular graph layout is a drawing scheme where all nodes are placed on the perimeter of a circle. An inherent issue with circular layouts is that the rigid restriction on node placement often gives rise to long edges and an overall dense drawing. We suggest here three independent, complementary techniques for lowering the density and improving the readability of circular layouts. First, a new algorithm is given for placing the nodes on the circle such that edge lengths are reduced. Second, we enhance the circular drawing style by allowing some of the edges to be routed around the exterior of the circle. This is accomplished with an algorithm for optimally selecting such a set of externally routed edges. The third technique reduces density by coupling groups of edges as bundled splines that share part of their route. Together, these techniques are able to reduce clutter, density and crossings compared with existing methods.
Measuring and extracting proximity in networks.
Measuring distance or some other form of proximity between objects is a standard data mining tool. Connection subgraphs were recently proposed as a way to demonstrate proximity between nodes in networks. We propose a new way of measuring and extracting proximity in networks called “cycle free effective conductance” (CFEC). Importantly, the measured proximity is accompanied with a proximity subgraph, which allows assessing and understanding measured values. Our proximity calculation can handle more than two endpoints, directed edges, is statistically well-behaved, and produces an effectiveness score for the computed subgraphs. We provide an efficient algorithm to measure and extract proximity. Also, we report experimental results and show examples for four large network data sets: a telecommunications calling graph, the IMDB actors graph, an academic co-authorship network, and a movie recommendation system.
Drawing Directed Graphs Using Quadratic Programming.
 We describe a new method for visualization of directed graphs. The method combines constraint programming techniques with a high performance force-directed placement (FDP) algorithm. The resulting placements highlight hierarchy in directed graphs while retaining useful properties of FDP; such as emphasis of symmetries and preservation of proximity relations. Our algorithm automatically identifies those parts of the digraph that contain hierarchical information and draws them accordingly. Additionally, those parts that do not contain hierarchy are drawn at the same quality expected from a nonhierarchical, undirected layout algorithm. Our experiments show that this new approach is better able to convey the structure of large digraphs than the most widely used hierarchical graph-drawing method. An interesting application of our algorithm is directional multidimensional scaling (DMDS). DMDS deals with low-dimensional embedding of multivariate data where we want to emphasize the overall flow in the data (e.g., chronological progress) along one of the axes. 
IPSep%2DCoLa An Incremental Procedure for Separation Constraint Layout of Graphs.
  We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data.
Stress Majorization with Orthogonal Ordering Constraints.
Abstract. The adoption of the stress-majorization method from multi-dimensional scaling into graph layout has provided an improved mathematical basis and better convergence properties for so-called “force-directed placement ” techniques. In this paper we give an algorithm for augmenting such stress-majorization techniques with orthogonal ordering constraints and we demonstrate several graphdrawing applications where this class of constraints can be very useful.
DIG%2DCOLA Directed Graph Layout through Constrained Energy Minimization.

One%2Ddimensional layout optimization
 In this paper we discuss a useful family of graph drawing algorithms, characterized by their ability to draw graphs in one dimension. We define the special requirements from such algorithms and show how several graph drawing tech-niques can be extended to handle this task. In particular, we suggest a novel op-timization algorithm that facilitates using the Kamada and Kawai model [17] for producing one-dimensional layouts. The most important application of the algorithms seems to be in achieving graph drawing by axis separation, where each axis of the drawing addresses different aspects of aesthetics.
Topological Fisheye Views for Visualizing Large Graphs.

Distributed Graph Layout for Sensor Networks.
Sensor network applications frequently require that the sensors know their physical locations in some global coordinate system. This is usually achieved by equipping each sensor with a location measurement device, such as GPS. However, low-end systems or indoor systems, which cannot use GPS, must locate themselves based only on crude information available locally, such as inter-sensor distances. We show how a collection of sensors, capable only of measuring distances to close neighbors, can compute their locations in a purely distributed manner, i.e. where each sensor communicates only with its neighbors. This can be viewed as a distributed graph drawing algorithm. We experimentally show that our algorithm consistently produces good results under a variety of simulated real-world conditions, and is relatively robust to the presence of noise in the distance measurements.
Graph Drawing by Stress Majorization.
One of the most popular graph drawing methods is based of achieving graphtheoretic target ditsances. This method was used by Kamada and Kawai [15], who formulated it as an energy optimization problem. Their energy is known in the multidimensional scaling (MDS) community as the stress function. In this work, we show how to draw graphs by stress majorization, adapting a technique known in the MDS community for more than two decades. It appears that majorization has advantages over the technique of Kamada and Kawai in running time and stability. We also present a few extensions to the basic energy model which can improve layout quality and computation speed in practice. Majorization-based optimization is essential to these extensions.
Distributed Graph Layout for Sensor Networks.
Sensor network applications frequently require that the sensors know their physical locations in some global coordinate system. This is usually achieved by equipping each sensor with a location measurement device, such as GPS. However, low-end systems or indoor systems, which cannot use GPS, must locate themselves based only on crude information available locally, such as inter-sensor distances. We show how a collection of sensors, capable only of measuring distances to close neighbors, can compute their locations in a purely distributed manner, i.e. where each sensor communicates only with its neighbors. This can be viewed as a distributed graph drawing algorithm. We experimentally show that our algorithm consistently produces good results under a variety of simulated real-world conditions, and is relatively robust to the presence of noise in the distance measurements.
Topological Fisheye Views for Visualizing Large Graphs.

Graph Drawing by Subspace Optimization.

Combining Hierarchy and Energy Drawing Directed Graphs.
We present an algorithm for drawing directed graphs, which is based on rapidly solving a unique onedimensional optimization problem for each of the axes. The algorithm results in a clear description of the hierarchy structure of the graph. Nodes are not restricted to lie on fixed horizontal layers, resulting in layouts that convey the symmetries of the graph very naturally. The algorithm can be applied without change to cyclic or acyclic digraphs, and even to graphs containing both directed and undirected edges. We also derive a hierarchy index from the input digraph, which quantitatively measures its amount of hierarchy.
Robust Linear Dimensionality Reduction.
We present a novel family of data-driven linear transformations, aimed at finding low dimensional embeddings of multivariate data, in a way that optimally preserves the structure of the data. The well-studied PCA and Fisher&#039;s LDA are shown to be special members in this family of transformations, and we demonstrate how to generalize these two methods such as to enhance their performance. Furthermore, our technique is the only one, to the best of our knowledge, that reflects in the resulting embedding both the data coordinates and pairwise similarities and/or dissimilarities between the data elements. Even more so, when information on the clustering (labeling) decomposition of the data is known, this information can also be integrated in the linear transformation, resulting in embeddings that clearly show the separation between the clusters, as well as their internal structure. All this makes our technique very flexible and powerful, and lets us cope with kinds of data that other techniques fail to describe properly.
Graph Drawing by High%2DDimensional Embedding.
We present a novel approach to the aesthetic drawing of undirected graphs. The method has two phases: first embed the graph in a very high dimension and then project it into the 2-D plane using PCA. Experiments we have carried out show the ability of the method to draw graphs of 10 nodes in few seconds. The new method appears to have several advantages over classical methods, including a significantly better running time, a useful inherent capability to exhibit the graph in various dimensions, and an effective means for interactive exploration of large graphs.
On Spectral Graph Drawing.
The spectral approach for graph visualization computes the layout of a graph using certain eigenvectors of related matrices. Some important advantages of this approach are an ability to compute optimal layouts (according to specific requirements) and a very rapid computation time. In this paper we explore spectral visualization techniques and study their properties. We present a novel view of the spectral approach, which provides a direct link between eigenvectors and the aesthetic properties of the layout. In addition, we present a new formulation of the spectral drawing method with some aesthetic advantages. This formulation is accompanied by an aesthetically-motivated algorithm, which is much easier to understand and to implement than the standard numerical algorithms for computing eigenvectors.
Axis%2Dby%2DAxis Stress Minimization.
Graph drawing algorithms based on minimizing the so-called stress  energy strive to place nodes in accordance with target distances. They were first  introduced to the graph drawing field by Kamada and Kawai [11], and they had  previously been used to visualize general kinds of data by multidimensional scaling.
Visualization of Labeled Data Using Linear Transformations.
We present a novel family of data-driven linear transformations, aimed at visualizing multivariate data in a low-dimensional space in a way that optimally preserves the structure of the data. The well-studied PCA and Fisher&#039;s LDA are shown to be special members in this family of transformations, and we demonstrate how to generalize these two methods such as to enhance their performance. Furthermore, our technique is the only one, to the best of our knowledge, that reflects in the resulting embedding both the data coordinates and pairwise similarities and/or dissimilarities between the data elements. Even more so, when information on the clustering (labeling) decomposition of the data is known, this information can be integrated in the linear transformation, resulting in embeddings that clearly show the separation between the clusters, as well as their intra-structure. All this make our technique very flexible and powerful, and let us cope with kinds of data that other techniques fail to describe properly.
A two%2Dway visualization method for clustered data.
We describe a novel approach to the visualization of hierarchical clustering that superimposes the classical dendrogram over a fully synchronized low-dimensional embedding, thereby gaining the benefits of both approaches. In a single image one can view all the clusters, examine the relations between them and study many of their properties. The method is based on an algorithm for lowdimensional embedding of clustered data, with the property that separation between all clusters is guaranteed, regardless of their nature. In particular, the algorithm was designed to produce embeddings that strictly adhere to a given hierarchical clustering of the data, so that every two disjoint clusters in the hierarchy are drawn separately.
Drawing Directed Graphs Using One%2DDimensional Optimization.
We present an algorithm for drawing directed graphs, which is based on  rapidly solving a unique one-dimensional optimization problem for each of the  axes. The algorithm results in a clear description of the hierarchy structure of  the graph. Nodes are not restricted to lie on fixed horizontal layers, resulting in  layouts that convey the symmetries of the graph very naturally. The algorithm  can be applied without change to cyclic or acyclic digraphs, and even to graphs  containing both directed and undirected edges. We also derive a hierarchy index  from the input digraph, which quantitatively measures its amount of hierarchy.
ACE A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs.
We present an extremely fast graph drawing algorithm for very large graphs, which we term ACE (for Algebraic multigrid Computation of Eigenvectors). ACE finds an optimal drawing by minimizing a quadratic energy function due to Hall, using a novel algebraic multigrid technique. The algorithm exhibits an improvement of something like two orders of magnitude over the fastest algorithms we are aware of; it draws graphs of a million nodes in less than a minute. Moreover, the algorithm can deal with more general entities, such as graphs with masses and negative weights (to be defined in the text), and it appears to be applicable outside of graph drawing too.
Graph Drawing by High%2DDimensional Embedding.
We present a novel approach to the aesthetic drawing of undirected graphs. The method has two phases: first embed the graph in a very high dimension and then project it into the 2-D plane using PCA. Experiments we have carried out show the ability of the method to draw graphs of 10 nodes in few seconds. The new method appears to have several advantages over classical methods, including a significantly better running time, a useful inherent capability to exhibit the graph in various dimensions, and an effective means for interactive exploration of large graphs.
ACE A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs.
We present an extremely fast graph drawing algorithm for very large graphs, which we term ACE (for Algebraic multigrid Computation of Eigenvectors). ACE finds an optimal drawing by minimizing a quadratic energy function due to Hall, using a novel algebraic multigrid technique. The algorithm exhibits an improvement of something like two orders of magnitude over the fastest algorithms we are aware of; it draws graphs of a million nodes in less than a minute. Moreover, the algorithm can deal with more general entities, such as graphs with masses and negative weights (to be defined in the text), and it appears to be applicable outside of graph drawing too.
A Fast Multi%2DScale Method for Drawing Large Graphs.
We present a multi-scale layout algorithm for the aesthetic drawing of  undirected graphs with straight-line edges. The algorithm is extremely  fast, and is capable of drawing graphs that are substantially larger than  those we have encountered in prior work. For example, the paper contains  a drawing of a graph with over 15,000 vertices. Also we achieve  &#034;nice&#034; drawings of 1000 vertex graphs in about 1 second. The proposed  algorithm embodies a new multi-scale scheme for drawing graphs, which  was motivated by the earlier multi-scale algorithm of Hadany and Harel  [HH99]. In principle, it could significantly improve the speed of essentially  any force-directed method (regardless of that method&#039;s ability of drawing  weighted graphs or the continuity of its cost-function).
On Clustering Using Random Walks.
We propose a novel approach to clustering, based on deterministic analysis of random walks on the weighted graph associated with the clustering problem. The method is centered around what we shall call \emph{separating operators}, which are applied repeatedly to sharpen the distinction between the weights of inter-cluster edges (the so-called separators), and those of intra-cluster edges. These operators can be used as a stand-alone for some problems, but become particularly powerful when embedded in a classical multi-scale framework and/or enhanced by other known techniques, such as agglomerative clustering. The resulting algorithms are simple, fast and general, and appear to have many useful applications.
Clustering spatial data using random walks.
Discovering significant patterns that exist implicitly in huge spatial databases is an important computational task. A common approach to this problem is to use cluster analysis. We propose a novel approach to clustering, based on the deterministic analysis of random walks on a weighted graph generated from the data. Our approach can decompose the data into arbitrarily shaped clusters of different sizes and densities, overcoming noise and outliers that may blur the natural decomposition of the data. The method requires only O(n log n) time, and one of its variants needs only constant space.
A Fast Multi%2DScale Method for Drawing Large Graphs.
We present a multi-scale layout algorithm for the aesthetic drawing of  undirected graphs with straight-line edges. The algorithm is extremely  fast, and is capable of drawing graphs that are substantially larger than  those we have encountered in prior work. For example, the paper contains  a drawing of a graph with over 15,000 vertices. Also we achieve  &#034;nice&#034; drawings of 1000 vertex graphs in about 1 second. The proposed  algorithm embodies a new multi-scale scheme for drawing graphs, which  was motivated by the earlier multi-scale algorithm of Hadany and Harel  [HH99]. In principle, it could significantly improve the speed of essentially  any force-directed method (regardless of that method&#039;s ability of drawing  weighted graphs or the continuity of its cost-function).
A Fast Multi%2Dscale Method for Drawing Large Graphs.
We present a multi-scale layout algorithm for the aesthetic drawing of  undirected graphs with straight-line edges. The algorithm is extremely  fast, and is capable of drawing graphs that are substantially larger than  those we have encountered in prior work. For example, the paper contains  a drawing of a graph with over 15,000 vertices. Also we achieve  &#034;nice&#034; drawings of 1000 vertex graphs in about 1 second. The proposed  algorithm embodies a new multi-scale scheme for drawing graphs, which  was motivated by the earlier multi-scale algorithm of Hadany and Harel  [HH99]. In principle, it could significantly improve the speed of essentially  any force-directed method (regardless of that method&#039;s ability of drawing  weighted graphs or the continuity of its cost-function).
